/**
 * Created by sunchenglin on 2017/7/17.
 * 插入排序
// 希尔排序
 //    冒泡排序
 //    选择排序
 //    插入排序
 //    计数排序
 //    桶排序
 //    基数排序
 //    拓扑排序
 //    外部排序
 */
public class Solution {


    public static void change(int[] array, int i, int j){
        int temp = array[i];
        array[i] =array[j];
        array[j] = temp;
    }
//往前找，比自己小的下移一位，比自己大的大的往后移动，然后插入。
    public static void insertSort(int[] array){
        int temp;
        for(int i=1; i<array.length; i++){
            int j=0;
            while(j<i){
                if(array[j]<=array[i])
                    j++;
                else
                    break;
            }
            if(j!=i){
                temp = array[i];
                for(int k=i-1;k>=j;k--){
                    array[k+1] = array[k];
                }
                array[j]=temp;
            }
        }
    }

    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        insertSort(a);
        System.out.println("haha");
    }
}
